#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
typedef struct AVL
{
    int data;
    int height;
    struct AVL *left, *right;
};
int height(AVL *p)
{
    if (!p)
        return 0;
    return p->height;
}
//  LL_rotation
//  Perform a rotate between a node (finder) and its left child
AVL *single_Rotation_LL(AVL *&finder)
{
    AVL *L = finder->left;
    finder->left = L->right;
    L->right = finder;
    //updata height then return new node
    finder->height = MAX(height(finder->left), height(finder->right)) + 1;
    L->height = MAX(height(L->left), height(L->right)) + 1;
    return L;
}
//  RR_rotation
//  Perform a rotate between a node (finder) and its right child
AVL *single_Rotation_RR(AVL *finder)
{
    AVL *R = finder->right;
    finder->right = R->left;
    R->left = finder;
    //updata height then return new node
    finder->height = MAX(height(finder->left), height(finder->right)) + 1;
    R->height = MAX(height(R->left), height(R->right)) + 1;
    return R;
}
//LR_rotation
AVL *double_Rotation_left_right(AVL *finder)
{
    //Perform a RR_rotation to the left_chiled of finder
    finder->left = single_Rotation_RR(finder->left);
    //then Perform a LL_rotation to the finder and return node
    return single_Rotation_LL(finder);
}
//RL_rotation
AVL *double_Rotation_right_left(AVL *finder)
{
    //Perform a LL_rotation to the right_chiled of finder
    finder->right = single_Rotation_LL(finder->right);
    //then Perform a RR_rotation to the finder and return node
    return single_Rotation_RR(finder);
}
AVL *insert(AVL *&Tree, int key)
{
    if (!Tree)
    {
        Tree = (AVL *)malloc(sizeof(AVL));
        Tree->data = key;
        Tree->height = 0;
        Tree->left = Tree->right = NULL;
    }
    else
    {
        //insert right
        if (key > Tree->data)
        {
            Tree->right = insert(Tree->right, key);
            if (height(Tree->right) - height(Tree->left) == 2)
            {
                if (key > (Tree->right)->data) //RR_rotation
                {
                    Tree = single_Rotation_RR(Tree);
                }
                else //RL_rotation
                {
                    Tree = double_Rotation_right_left(Tree);
                }
            }
        }
        if (key < Tree->data)
        {
            Tree->left = insert(Tree->left, key);
            if (height(Tree->left) - height(Tree->right) == 2)
            {
                if (key < Tree->left->data) //LL_rotation
                {
                    Tree = single_Rotation_LL(Tree);
                }
                else
                {
                    Tree = double_Rotation_left_right(Tree);
                }
            }
        }
    }
    //updata height
    Tree->height = MAX(height(Tree->left), height(Tree->right)) + 1;
    return Tree;
}
void initia(AVL *&root, int a[], int n)
{
    root = NULL;
    for (int i = 0; i < n; i++)
    {
        insert(root, a[i]);
    }
}
void midorder_transverval(AVL *root)
{
    if (root)
    {
        midorder_transverval(root->left);
        printf("%4d", root->data);
        midorder_transverval(root->right);
    }
}
int main()
{
    /*******************code*******************/
    int a[] = {34, 23, 15, 98, 115, 28, 107};
    AVL *tree;
    initia(tree, a, 5);
    midorder_transverval(tree);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
